package com.note.feng.leetcode.algorithms.easy.seven;

public class SevenHundredFourtyFour {
    /**
     * 744 寻找比目标字母大的最小字母
     * 给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。
     *
     * 在比较时，字母是依序循环出现的。举个例子：
     *
     * 如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b']，则答案返回 'a'
     *
     * 示例 1：
     *
     * 输入: letters = ["c", "f", "j"]，target = "a"
     * 输出: "c"
     * 示例 2:
     *
     * 输入: letters = ["c","f","j"], target = "c"
     * 输出: "f"
     * 示例 3:
     *
     * 输入: letters = ["c","f","j"], target = "d"
     * 输出: "f"
     *
     * 提示：
     *
     * 2 <= letters.length <= 104
     * letters[i] 是一个小写字母
     * letters 按非递减顺序排序
     * letters 最少包含两个不同的字母
     * target 是一个小写字母
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/find-smallest-letter-greater-than-target
     */
    /**
     * 解法：线性查找
     * 如果 target 大于等于数组的最后一个元素，直接返回数组的第一个元素；
     * 否则，数组中一定存在大于 target 的元素，从头开始遍历数组即可
     * @param letters
     * @param target
     * @return
     */
    public char nextGreatestLetter(char[] letters, char target) {
        int left = 0, right = letters.length - 1;
        if(target >= letters[right] || target < letters[0]){
            return letters[0];
        }
        for (int i = 0; i < right; i++) {
            if(letters[i] <= target && letters[i + 1] > target){
                return letters[i + 1];
            }
        }
        return letters[0];
    }
}
